|
|
Vyhledání nejdelšího shodného prefixu
Chrastina, Ondřej ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Tato práce se zabývá problémem efektivního směrování a klasifikací dat v počítačových sitích, konkrétně vyhledáním nejdelšího shodného prefixu pro síťový protokol verze 6. Jsou vybrány algoritmy Binary Trie, Level Compressed Trie, Lulea Compressed Trie a Binary Search on Intervals, které jsou nejdříve popsány a poté testovány s cílem najít nejvhodnější algoritmus z hlediska pamětových nároků a rychlosti vyhledání.
|
|
|
Vizualizace algoritmů pro vyhledání nejdelšího shodného prefixu
Fomiczew, Jiří ; Matoušek, Jiří (oponent) ; Kováčik, Michal (vedoucí práce)
Tato práce se zabývá návrhem a implementací programu pro vizualizaci algoritmů pro vyhledání nejdelšího shodného prefixu (LPM), což je jedna z nejdůležitějších operací při klasifikaci a směrování paketů v sítích TCP/IP. Je popsána jak základní teorie, tak vybrané algoritmy - Trie, Tree Bitmap a CPE. Dále je popsán návrh a implementace programu pro vizualizaci vyhledávacího procesu těchto algoritmů s důrazem na možné použití pro pedagogické účely. Nakonec jsou probrány možnosti budoucího vývoje a rozšíření programu.
|
|
|
Grafická demonstrace vybraného algoritmu pro vyhledání směru
Ohrádka, Marek ; Kaštil, Jan (oponent) ; Puš, Viktor (vedoucí práce)
Tato bakalářská práce se zabývá problematikou směrování v IP sítích, popisuje různé směrovací protokoly. Ukazuje možná řešení vyhledávání nejdelšího shodného prefixu, výhody a nevýhody jednotlivých řešení. Popisuje strukturu trie a její varianty. Detailně popisuje strukturu shape shifting trie, metodu jejího vytváření a způsob průchodu touto strukturou - vyhledávací algoritmus SST. Popisuje návrh a implementaci aplikace, která graficky demonstruje průběh vyhledávání v datové struktuře SST. Popisuje dekompozici problému a způsob jejího řešení v implementaci.
|
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Sedlář, František ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
V této bakalářské práci byly popsány základní algoritmy pro vyhledání nejdelšího shodného prefixu (LPM). K již existujícím implementacím v knihovně Netbench byl přidán další algoritmus - LC Trie. Všechny algoritmy, které knihovna obsahuje, byly testovány nad reálnými množinami IPv6 prefixů. Na základě zde získaných dat byly navzájem porovnány. Dále byly sepsány skripty pro stahování prefixů z významných zdrojů na internetu a testovací skripty k jednotlivým algoritmům.
|
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Sedlář, František ; Matoušek, Jiří (oponent) ; Tobola, Jiří (vedoucí práce)
Tato diplomová práce nejprve uvádí čtenáře do problematiky vyhledávání nejdelších shodných prefixů. Analyzuje a popisuje vybrané algoritmy se zaměřením na jejich rychlost, paměťovou náročnost a vhodnost pro hardwarovou implementaci. Na základě získaných poznatků představuje nový algoritmus Generic Hash Tree Bitmap. Ten je mnohonásobně rychlejší než jiné používané metody, zatímco jeho paměťové nároky jsou mnohdy nižší. Implementace algoritmu se stala součástí knihovny Netbench.
|
|
|
Vyhledání nejdelšího shodného prefixu
Weigner, Martin ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Rychlost počítačových sítí se neustále zvyšuje. Jednou ze základních úloh, které musí síťová zařízení provádět, je vyhledávání nejdelšího shodného prefixu. Mnoho algoritmů tuto úlohu dokáže řešit, ale je nutné tuto úlohu řešit velmi rychle, a to především z toho důvodu, že se stále zvyšují přenosové rychlosti a nastupuje směrovací standard IPv6. Ten má delší adresy, a je tedy nutné vyhledávat prefixy ve větších množinách. V práci jsou popsány současné algoritmy. Ty jsou porovnány v konfrontaci s novým algoritmem HashTreeBitmap, který je v práci popsán. Na základě testů je doloženo, že tento algoritmus je schopen zvládat vysoké nároky, které jsou na něj kladeny.
|
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Suchodol, Jaroslav ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Práce se zabývá směrováním v IP sítích, konkrétněji otázkou zjištění nejdelšího shodného prefixu. Problematiku vyhledání nejdelšího shodného prefixu řeší mnoho sofistikovaných algoritmů. Hlavním úkolem této práce je zaměření na následující algoritmy - Controlled Prefix Expansion, Lulea Compressed Tries, Binární vyhledávání na intervalech a Binární vyhledávání na prefixech. Algoritmy jsou principiálně popsány a následně softwarově implementovány v jazyce Python. Výstup práce spočívá v analýze/porovnání jednotlivých algoritmů z hlediska paměťové náročnosti a počtu přístupů do paměti v nejhorším případě.
|
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Skačan, Martin ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Tato práce se zabývá algoritmy pro vyhledání nejdelšího shodného prefixu (longest prefix match - LPM), což je klíčová operace při klasifikaci paketů a směrování v počítačových IP sítích. Je uvedena potřebná teorie a rozbor vybraných algoritmů - Trie, Tree Bitmap, Shape Shifting Tree a Multi-Match. Tyto metody byly detailně popsány a implementovány v programovacím jazyce Python. Nad implementovanými algoritmy byly provedeny testy a simulace pro určení jejich praktických paměťových nároků s cílem identifikovat nejvhodnější metodu pro množiny prefixů o velikosti desítek až tisíců pravidel.
|
|
|
Vyhledávání nejdelšího shodného prefixu ve vysokorychlostních sítích
Skačan, Martin ; Tobola, Jiří (oponent) ; Kořenek, Jan (vedoucí práce)
Tato práce se zabývá vyhledáváním nejdelšího shodného prefixu (LPM), což je časově kritická operace při směrování paketů. Pro dosažení propustnosti 100Gbps je nutná hardwarová implementace této operace a směrovací tabulka musí být uložena v paměti na čipu, která je omezena nízkou kapacitou. Současné LPM algoritmy vyžadují velké množství paměti pro uložení směrovacích tabulek protokolu IPv6, nebo je není možno jednoduše implementovat v HW. Proto jsem se zaměřil na analýzu směrovacích tabulek IPv6 a několika známých LPM algoritmů. Na základě této analýzy jsem navrhl nový algoritmus, který vyniká nízkou paměťovou složitostí pro IPv4/IPv6 vyhledávání. Navržený algoritmus má nejnižší paměťové nároky v porovnání s existujícími LPM algoritmy. Navíc je vhodný pro nasazení ve vysokorychlostních 100Gbps sítích, což bylo ukázáno s pomocí nové hardwarové architektury využívající zřetězené zpracování s propustností 140Gbps.
|
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Kováčik, Michal ; Tobola, Jiří (oponent) ; Kořenek, Jan (vedoucí práce)
Táto práce je zaměřená na algoritmy pro vyhledávání nejdelšího shodného prefixu (LPM), což je klíčová operace při směrování a klasifikaci paketů v sítích TCP/IP. Spolu s potřebnou teorií je věnován prostor zhodnocení běžně používaných algoritmů s důrazem na jejich rychlost a paměťovou efektivitu. Zaměření se pak orientuje na síte IPv6, jejich typické množiny prefixů a porovnávání vhodných algoritmů. Pak je pro vybraný algoritmus navržena optimalizace a je provedena její implementace v programovacím jazyce Python.
|
host ::
RSS.